public class L654 {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        new Solution().constructMaximumBinaryTree(nums);
    }

    static class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums.length == 0) {
                return null;
            }

            return treeHelper(nums, 0, nums.length);

        }

        private TreeNode treeHelper(int[] nums, int left, int right) {
            if (left >= right) return null;

            int maxIndex = left;
            for (int i = left; i < right; i++) {
                maxIndex = nums[maxIndex] > nums[i] ? maxIndex : i;
            }
            TreeNode root = new TreeNode(nums[maxIndex]);
            root.left = treeHelper(nums, left, maxIndex);
            root.right = treeHelper(nums, maxIndex + 1, right);
            return root;
        }
    }
}
